class Solution {
public:
    string replaceSpace(string s) {
        //原地置换空格，不需要新建字符串
        //时间复杂度O(n),空间复杂度O(1)

        int count = 0;  //统计空格个数
        int slen = s.size();  //原字符串长度,不包括末尾的'\0'字符

        for(int m = 0; m < slen; ++m){
            if(' ' == s[m])
            count++;
        }

        //若为空字符串或者字符串中不含空格，则返回原字符串
        if((0 == slen) || (0 == count))   return s;

        int i = slen - 1;  //前指针指向旧字符串末尾
        int j = slen + 2 * count;  //新扩展字符串长度
        s.resize(j);
        s[j] = '\0';
        j--;  //后指针指向新字符串末尾

        //双指针法
        while(i != j){
            if(' ' == s[i]){
                s[j] = '0';
                s[j - 1] = '2';
                s[j - 2] = '%';
                j = j - 3;
                i--;
            }else{
                s[j] = s[i];
                j--;
                i--;
            }
        }

        return s;
    }
};